package Algorithm;

import java.util.*;

public class test7 {
    // 给你一个整数数组nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k
    // 同时还满足nums[i] + nums[j] + nums[k] == 0
    // 你返回所有和为0且不重复的三元组
    // 算法原理: 排序, 双指针
    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        int n = nums.length;
        List<List<Integer>> list = new ArrayList<>();
        // 排序
        Arrays.sort(nums);
        for (int i = 0; i < n; ) { // 固定a
            // 小优化
            if (nums[i] > 0) break;
            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right) {
                // 判断
                if (nums[left] + nums[right] > target) {
                    right--;
                } else if (nums[left] + nums[right] < target) {
                    left++;
                } else {
                    // 添加符合的三元组
                    list.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
                    // 缩小区间继续寻找
                    left++; right--;
                    // 去重left, right 并且注意不能越界
                    while (nums[left] == nums[left - 1] && left < right) {
                        left++;
                    }
                    while (nums[right] == nums[right + 1] && left < right) {
                        right--;
                    }
                }
            }
            // 对a进行去重, 注意不能越界
            i++;
            while (i < n && nums[i] == nums[i - 1]) {
                i++;
            }
        }
        System.out.println(list);
    }
}
